// https://leetcode.cn/problems/two-sum/description/

// 算法思路总结：
// 1. 使用哈希表存储数字到索引的映射
// 2. 遍历数组，计算目标差值
// 3. 在哈希表中查找差值是否存在
// 4. 找到则返回索引对，否则记录当前数字
// 5. 时间复杂度：O(n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <vector>
#include <unordered_map>

class Solution
{
public:
    vector<int> twoSum(vector<int>& nums, int target)
    {
        int n = nums.size();
        unordered_map<int, int> up;

        for (int i = 0; i < n; i++)
        {
            int goal = target - nums[i];
            if (up.count(goal) > 0)
                return {up[goal], i};
            else
                up[nums[i]] = i;
        }
        return {};
    }
};

int main()
{
    vector<int> v1 = {2, 7, 11, 15}, v2 = {3, 2, 4};
    int t1 = 9, t2 = 6;

    Solution sol;

    auto r1 = sol.twoSum(v1, t1);
    auto r2 = sol.twoSum(v2, t2);

    for (auto& num : r1)
        cout << num << " ";
    cout << endl;

    for (auto& num : r2)
        cout << num << " ";
    cout << endl;

    return 0;
}